home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 001-025 / disk_006 / sort / sortc.c < prev    next >
C/C++ Source or Header  |  1992-05-06  |  38KB  |  1,413 lines
  1. /*
  2.  *                s o r t c . c
  3.  *
  4.  * Sort utility
  5.  */
  6.  
  7. /*)BUILD
  8.         $(PROGRAM)    = sortc
  9.         $(FILES)    = { sortc qksort }
  10.         $(TKBOPTIONS) = {
  11.             TASK     = ...SOR
  12.             ACTFIL    = 6
  13.             UNITS    = 6
  14.         }
  15. */
  16.  
  17. #ifdef    DOCUMENTATION
  18.  
  19. title    sort    Sort Data Files
  20. index        Sort Data Files
  21.  
  22. synopsis
  23.  
  24.     sortc [-options] [-oOUTFILE] [file ...]
  25.  
  26. description
  27.  
  28.     Sortc sorts all of the named files together and writes the result
  29.     to the standard output or to the file named in the -o option.
  30.     The standard input is sorted if no file names are supplied; sort
  31.     may thus be used as a filter.
  32.     .s
  33.     The output file may be the same as one of the input files.
  34.     .s
  35.     The default sort is ascending in ASCII collating sequence
  36.     using the entire line.  Upper and lower case are considered
  37.     different.  Using optional arguments, up to ten key fields
  38.     may be specified.  Lines with equal keys are further ordered
  39.     using the entire line as a single ASCII key.
  40.     .s
  41.     The following options apply to the entire sort:
  42.     .s.lm +4
  43.     .s.i-4;-o##The sorted output is written to the named file
  44.     instead of to the standard output.  The file may be the
  45.     same as one of the input files.
  46.     .s.i-4;-u##(Unique) only the first of a set of lines
  47.     having equal keys is output.  Only the specified keys are
  48.     considered in the definition of 'unique.'
  49.     .s.i-4;-v##(Verbose) Print elapsed time, etc.
  50.     .s.lm -4
  51.     The following options define the form of the sort.  If they
  52.     preceed the first key field definition, they define the default
  53.     for all keys.  If the option includes a key definition, only
  54.     that key is affected.
  55.     .s.lm +4
  56.     .s.i-4;-b##(Blank) causes leading whitespace in the key
  57.     field to be ignored.
  58.     .s.i-4;-d##(Dictionary) sorts in dictionary order;  only
  59.     letters, digits, and blanks are considered in the compare,
  60.     all else is ignored.  (Note: national letters (with values greater
  61.     than 128 decimal) are not processed correctly.)
  62.     .s.i-4;-f##(Fold case) folds all letters to lower-case for
  63.     comparisons.
  64.     .s.i-4;-i##(Ignore whitespace) causes all non-printing characters
  65.     to be ignored.
  66.     .s.i-4;-k##(Key) selects a field to be used as a sort key.
  67.     Up to ten key fields can be specified.  The keys are in order
  68.     of decreasing significance.  Key fields are compared, beginning
  69.     with the most significant one, until a not-equal key is found.
  70.     .s
  71.     The format of the -k option is "-kM1.N1,M2.N2"  The formatting
  72.     flags "bdfinrt?" may be applied to a particular key by preceeding
  73.     the 'k' appropriately as will be shown in the examples.
  74.     .s
  75.     The values following the "-k" define the starting and ending
  76.     position of the key using a field/offset value:
  77.     .lm+8
  78.     .s.i-8;M1.N1##Start of the key position (first character that
  79.     is to be compared).
  80.     .s.i-8;M2.N2##End of the key position (first character after
  81.     the key).
  82.     .lm-8
  83.     The 'M' values define the number of fields to skip, from the
  84.     start of the data line.  (0 means "skip no fields").
  85.     .s
  86.     The 'N' values define the number of bytes to skip in the
  87.     selected field.
  88.     .s
  89.     If "M1.N1" are omitted, start at the beginning of the line.
  90.     If "M2.N2" are omitted, end at the end of the line.
  91.     Except for "M2.N2" being omitted, omitting any of the four
  92.     values means "use zero" for that value.
  93.     .s
  94.     Neither of these specifiers will go beyond the end of the line.
  95.     A record can have a null key if the start-of-key is on or
  96.     after the end-of-key or at or after the end-of-line.
  97.     A null key is lower than any non-null key.
  98.     .s
  99.     If -b was specified, leading whitespace is skipped after
  100.     advancing to the M1 (M2) field, but before advancing by
  101.     N1 (N2) characters.
  102.     .s.i-4;-n##(Numeric) changes the sort ordering to ascending
  103.     arithmetic on a leading signed integer numeric string.
  104.     .s.i-4;-r##(Reverse) changes the sort ordering from ascending
  105.     to descending.
  106.     .s.i-4;-t?#(Terminator) changes the field terminator.  The
  107.     new definition is:
  108.     .s.lm+4
  109.     String of zero or more characters ending with the '?' character.
  110.     .s.lm-4
  111.     The terminator character may be escaped by using the backslash
  112.     convention.  By default, whitespace (blanks or tabs) terminates
  113.     a field.
  114.     .lm-4
  115.  
  116. Examples of Key Field Selection
  117.  
  118.     .br;Let a record be "ABC#DEF##########GHI"
  119.     .s.nf
  120.     Flag        Key field
  121.     -k1        " DEF         GHI"
  122.     -bk1        "DEF         GHI"
  123.     -bk1.1        "EF         GHI"
  124.     -bk1,2        "DEF         "
  125.     -k1,1        "" (Null field)
  126.     -k1.0,2.1    " DEF "
  127.     -bk1.0,2.1    "DEF         G"
  128.     -k0.1,1.3    "BC DE"
  129.     -k1.0,2.0    " DEF"
  130.     -k0.5,1.0    "" (Null field)
  131.     .s.f
  132.     Let a record be "ABC,DEFGHIJ,KLM"
  133.     .s.nf
  134.     Flag        Key field
  135.     -t,k1        "DEFGHIJ,KLM"
  136.     -t,k1,2        "DEFGHIJ,"
  137.     -t,k0.1,0.6    "BC,DE"
  138.     -t,k1.0,0.10    "DEFGHI"
  139.     .f    
  140.  
  141. Files
  142.  
  143.     sort.tmp
  144.  
  145. diagnostics
  146.  
  147.     The following messages occur on a non-severe error. SORTC
  148.     will exit with "error" status.
  149.  
  150.     .lm +8
  151.     .s.i -8;"?SORT-F-Cannot create temp. file"
  152.     .br
  153.     The required temporary file cannot be created  in  the
  154.     current directory.
  155.     .s.i -8;"?SORT-F-Cannot open input file."
  156.     .br
  157.     An input file cannot be accessed for reading.
  158.     .s.i -8;"?SORT-F-Cannot create output file."
  159.     .br
  160.     An output file cannot be  created  for writing.
  161.     .s.i -8;"?SORT-F-Out of space."
  162.     .br
  163.     There was insufficient memory space for the sort.
  164.     .lm -8
  165.     The following messages occur on a severe error. SORT will
  166.     exit with "severe error" status. Get help.
  167.     .s
  168.     .nf
  169.     "?SORT-U-Unexpected end of file"
  170.     "?SORT-U-Empty run"
  171.     "?SORT-U-temp. file"
  172.     .f
  173. author
  174.  
  175.     David Conroy
  176.     .s
  177.     Very slightly modified by Martin Minow
  178.     .s.nf
  179.     Extensively modified by
  180.       Ray Van Tassle
  181.       Motorola
  182.       1301 E. Algonquin Rd.
  183.       Room 4135
  184.       Shaumburg, Ill.
  185.       (312)-576-6017
  186.  
  187. Bugs
  188.  
  189. Internal
  190.  
  191.     See the source of sortc.c for a discussion of Workfile strategies
  192.     and sort timings.
  193.  
  194. #endif
  195.  
  196. /*--- EDIT # 0492    27 Apr 1982   13:01:26    DB1:[21,6]SORTX.C;1077  */
  197. /*--- PREVIOUS EDIT    27 Apr 1982   12:59:18    DB1:[21,6]SORTX.C;1076  */
  198. /*
  199.  * Edit history (after 0492)
  200.  * 22-Jun-82    MM    Changed systime call to use library ftime routine.
  201.  */
  202.  
  203. /*
  204.  *
  205.  *   
  206.  * Work-file(s)
  207.  *   This program uses a Quicksort for the distribution phase (creating
  208.  *   runs of sorted lines) and puts each run into a work file. In essence,
  209.  *   the merge is one n-way merge onto the output file. ("n" is the number
  210.  *   of runs created in the 1st pass, as the file position is saved for each
  211.  *   run).
  212.  *   
  213.  * During the distribution (input) phase, the sorted array (line)
  214.  * is used as a heap while putting the run out to the work file.
  215.  * We replace the lines with input lines, to attempt to increase the size
  216.  * of the run. It is muchly and widely claimed that this doubles the
  217.  * average run size.
  218.  * My experiments bear this out. This should make the merge phase
  219.  * go faster (less runs).
  220.  * Oh hell. It turns out that doing so greatly increases the time
  221.  * of the distribution phase (50% to 100%) but decreases the time of the
  222.  * merge phase only a little bit. Perhaps it would help
  223.  * in a very specialized environment, where you could make several
  224.  * merge work-files, all on different devices, and have them contiguous,
  225.  * so that you wouldn't have the overhead of arm seeks.
  226.  * The absolute best you could ever hope to do would require 2 passes
  227.  * over the data: one for the distribution phase, and one for
  228.  * the merge phase. According to one of my books, about the best
  229.  * thing to use with several work files is a "three file polyphase merge",
  230.  * with a Fibonacci series for the number of runs on each file.
  231.  * The quoted figures are 2.7-4.6 equivalent passes over the entire data
  232.  * (polyphase is rough to figure exactly, because it does not pass the
  233.  * entire file on each pass).
  234.  * My figures on several varied files are the entire sort taking anywhere
  235.  * from 3 to 5 times as long as just passing the file thru a pgm which
  236.  * converts it to lower case. This seems quite good, as the time spent
  237.  * in doing comparisons is hefty. Maybe changine the way we do the
  238.  * merge could improve things a lot, but I don't think so. Anyway, this
  239.  * is a pretty neat trick, cramming all the runs into one file.
  240.  *
  241.  *
  242.  * I also pre-read several lines from each run whenever I do a seek
  243.  * to that run (this is H_P_READ). This improves the time of the merge
  244.  * phase by making it as much as ten (!!!) times faster. Evidently,
  245.  * the seek time is the dominating factor of this phase, and
  246.  * reading in several lines at each seek buys us a whole lot. Note that
  247.  * each actual read operation gets 512 bytes, which is usually several
  248.  * lines, so we have done all the work to get many lines, so
  249.  * we might as well take advantage of that fact and save some of them.
  250.  * It turns out that there is very little to be gained by increasing the
  251.  * size of the pre-read from 5 to 10 lines. I suspect that most
  252.  * of the improvement is in going from none to 1, and each incremental line
  253.  * that is added gains less than the last.
  254.  *
  255.  * Doing all these things, and increasing the size of the in-core sort
  256.  * area (MX_RLINE) will make this a pretty fast sort program.
  257.  *
  258.  * Some timings:
  259.  * which    distr    merge    runs (distr,merge times in seconds 11/70)
  260.  *     Orig    327.2    146.1    214    Joe Sventeks DICT 45000 words
  261.  *    This    171    177    75    same (The file is already sorted)
  262.  *    pass    117            convert it to lower case (pass it)
  263.  *
  264.  *    orig    96.4    2038    161    32000 random numbers (ascii sort)
  265.  *    this    174    271    54    same
  266.  *    pass    111
  267.  *
  268.  *    orig    17.3    100.7    49    words.doc (9628 words)
  269.  *    this    40    61    17
  270.  *    pass    23
  271.  *
  272.  */
  273. #include <stdio.h>
  274.  
  275. #ifdef unix
  276. #include    <sys/types.h>
  277. #include    <sys/timeb.h>
  278. #else
  279. #ifndef AMIGA
  280. #include    <timeb.h>
  281. #endif
  282. #endif
  283.  
  284. #ifndef TRUE
  285. #define TRUE (1)
  286. #endif
  287.  
  288. #ifndef FALSE
  289. #define FALSE (0)
  290. #endif
  291.  
  292. #ifndef EOS
  293. #define EOS '\000'
  294. #endif
  295.  
  296. #define MX_RLINE 600    /* number of lines in a run */
  297. #define TEMP    "sort.tmp"
  298. #define MAX_WK_FILES 1    /* # of different work-files to use */
  299. #define MAX_KEYS 11    /* Max number of key fields that can be specified */
  300. #define H_P_READ 8    /* # of lines a heapelt can hold */
  301.  
  302. typedef char BYTE;
  303.  
  304. /*********** */
  305. /* These change the way internal routines perform */
  306. #define TREEVER    /* verify the tree after doing the reheap */
  307. #undef TREEVER
  308. #define REPLPUT     /* read replacement lines in putline */
  309. #undef REPLPUT
  310.  
  311. struct work_file {
  312.    char w_filename[35];
  313.    FILE *w_fp;
  314. };
  315.  
  316. struct    run {
  317.    struct run *r_rp;
  318.    long r_seek;
  319.    int r_size;
  320. };
  321.  
  322. struct heap_s {
  323.    char *h_lp_a[H_P_READ];
  324.    struct run *h_rp;
  325. };
  326.  
  327. struct    run *crp  = NULL;    /* current run ptr */
  328. struct    run *frp  = NULL;    /* 1st run ptr */
  329. struct    run *lrp  = NULL;    /* last run ptr */
  330.  
  331. struct work_file wkf[MAX_WK_FILES];
  332.  
  333. char **line = NULL;
  334. int first_out = TRUE;    /* This is the 1st output line */
  335.  
  336. FILE    *ofp = NULL;
  337. FILE    *tfp    = NULL;
  338. FILE    *ifp    = NULL;
  339. char    *ofn    = NULL;
  340. struct    heap_s *heap;
  341. int    nline    = 0;
  342. int    nruns    = 0;
  343. int max_mline = 0;    /* max # of lines we can hold in memory during merge*/
  344. int pre_lines = 0;    /* # of lines actually pre-read into memory */
  345.  
  346. long int in_records = 0;    /* # of records read from the input files */
  347. long int in_bytes = 0;        /* # of bytes in them */
  348.  
  349. static char lbuf[256];        /* Input line buffer */
  350.  
  351. static char *documentation[] = {
  352.     "-b  ignore leading blanks",
  353.     "-d  dictionary order",
  354.     "-f  fold letters to lowercase for compare",
  355.     "-i  ignore non-printing chars",
  356.     "-km1.n1,m2.n2 select key field (max 9 keys)",
  357.     "-n  numeric comparison",
  358.     "-oOUT  specify output file (otherwise it is stdout)",
  359.     "-r  reverse order to descending",
  360.     "-t? specify field terminator char",
  361.     "-u  output only 1st line with equal keys",
  362.     "-v  verbose",
  363.     NULL
  364. };
  365.  
  366. int nlbuf = -1;    /* length of string in lbuf (<0 means none) */
  367. char    **llout = NULL;    /* last line put out (for -u) */
  368.  
  369. int    dflag[MAX_KEYS];    /* dictionary order */
  370. int    iflag[MAX_KEYS];    /* ignore all whitespace */
  371. int    fflag[MAX_KEYS];    /* fold upper-case to lower-case */
  372. int    vflag = 0;        /* give elapsed times, etc */
  373. int    hard_way[MAX_KEYS];    /* if any of the above are set, this
  374.                 * comparison must be done the hard way.*/
  375. int    uflag = 0;        /* only output 1st of set of lines with
  376.                 * equal keys */
  377. int    nflag[MAX_KEYS];    /* numeric comparison (else alphabetic) */
  378. int    rflag[MAX_KEYS];    /* reverse sort sense
  379.                 * (descending instead of ascending) */
  380. int    bflag[MAX_KEYS];    /* ignore leading whitespace */
  381. char term_char[MAX_KEYS];    /* field terminator character */
  382. int    kflag = 0;        /* number of field specifiers (0 = none) */
  383.  
  384. /***** m1/n1 specify the 1st character of the key */
  385. int    m1[MAX_KEYS];        /* fields to skip to start-of-key */
  386. int    n1[MAX_KEYS];        /* chars to skip from start-of-field */
  387.  
  388. /***** m2/n2 specify the 1st character after the key. This char isn't
  389.  *    included in the key. */
  390. int    m2[MAX_KEYS];        /* Number of fields to skip to end-of-key.
  391.                  * -1 means 'end of line' */
  392. int    n2[MAX_KEYS];        /* chars to skip from end-of-key field */
  393.  
  394. extern    char *getline();
  395. extern  char *xalloc();
  396. extern int compare();    /* compare routine */
  397. extern qksort();    /* the sorting routine */
  398. struct heap_s heap_tmp;    /* temp area for the reheap */
  399.  
  400. #ifdef TIMER
  401. extern long int systime();    /* time in msec since midnight */
  402. long int start_time;
  403. #endif
  404.  
  405. main(argc, argv)
  406. char *argv[];
  407. {
  408.    register struct run *rp;
  409.    register char *cp;
  410.    char *cptmp;
  411.    char *argsave;
  412.    struct heap_s *hp;
  413.    int c, i, nf;
  414.  
  415. #ifdef TIMER
  416.    start_time = systime();        /* init for elapsed time */
  417. #endif
  418.    for (i = 0; i < MAX_KEYS; i++) {
  419.       m2[i] = -1;
  420.    }
  421.    nf = argc - 1;
  422.    for (i=1; i<argc; ++i) {
  423.       cp = argsave = argv[i];
  424.       if (*cp == '-') {
  425.      --nf;
  426.      argv[i] = NULL;
  427.      ++cp;
  428.      while (c = *cp++) {
  429.         switch (tolower(c)) {
  430.  
  431.         case 'v':
  432.            vflag++;
  433.            break;
  434.  
  435.         case 'n':
  436.            ++nflag[kflag];
  437.            break;
  438.  
  439.         case 'b':
  440.            ++bflag[kflag];
  441.            break;
  442.  
  443.         case 'd':
  444.            ++dflag[kflag];
  445.            ++hard_way[kflag];
  446.            break;
  447.  
  448.         case 'i':
  449.            ++iflag[kflag];
  450.            ++hard_way[kflag];
  451.            break;
  452.  
  453.         case 'f':
  454.            ++fflag[kflag];
  455.            ++hard_way[kflag];
  456.            break;
  457.  
  458.         case 'u':
  459.            ++uflag;
  460.            break;
  461.  
  462.         case 'o':
  463.            if (*cp == NULL) {     /* value is next arg */
  464.           if (++i >= argc)
  465.              usage("argument need after", argsave, c);
  466.                     /* no next arg, error! */
  467.           if (*(ofn = argv[i]) == '-')
  468.              usage("next argument may not be an option", argsave, c);
  469.                     /* next arg is itself an arg!! */
  470.           argv[i] = NULL;    /* eliminate the arg    */
  471.            }
  472.            else {        /* value is in this arg */
  473.           ofn = cp;
  474.            }
  475.            cp = argv[i];    /* re-examine current arg (to skip it) */
  476.            --nf;
  477.            break;
  478.  
  479.         case 'r':
  480.            ++rflag[kflag];
  481.            break;
  482.  
  483.         case 'k':
  484.            defin_key(cp);
  485.            kflag++;
  486.            m1[kflag] = n1[kflag] = n2[kflag] = 0; m2[kflag] = -1;
  487.            bflag[kflag] = rflag[kflag] = nflag[kflag] = 0;
  488.            iflag[kflag] = fflag[kflag] = dflag[kflag] = 0;
  489.            hard_way[kflag] = term_char[kflag] = 0;
  490.            cp = &argv[i];
  491.            break;
  492.  
  493.         case 't':
  494.            if ((c = *cp++) == EOS)
  495.             usage("no field separator after 't' option",
  496.                 argsave, c);
  497.            if (c == '\\') {        /* escaped char */
  498.           if (*cp == NULL)
  499.             usage("no field separator after 't\\' option",
  500.                 argsave, c);
  501.           cptmp = cp;
  502.           c = esc_char(&cptmp);   cp = cptmp;
  503.            }
  504.            term_char[kflag] = c;
  505.            break;
  506.  
  507.         default:
  508.            usage("unknown option", argsave, c);
  509.         }
  510.      }
  511.       }
  512.    }
  513.    if (nf == 0)
  514.       ifp = stdin;
  515.    if ((tfp = fopen(TEMP, "w")) == NULL) {
  516.       fprintf(stderr, "Cannot create temp file.\n");
  517.       exit(1);
  518.    }
  519. #ifdef AMIGA || unix
  520.    strcpy (wkf[0].w_filename, TEMP);
  521. #else
  522.    fgetname(tfp, wkf[0].w_filename);
  523. #endif
  524.    line = xalloc(MX_RLINE * sizeof(char *));
  525.    crp = xalloc(sizeof(struct run));
  526.    crp->r_size = 0;
  527. /* There is always an implied last key of: ascii, ascending order,
  528.  *    using the entire line.
  529.  */
  530.    if (kflag == 0) {
  531.       kflag++;
  532.    }
  533.    m1[kflag] = n1[kflag] = n2[kflag] = 0; m2[kflag] = -1;
  534.    bflag[kflag] = rflag[kflag] = nflag[kflag] = 0;
  535.    iflag[kflag] = fflag[kflag] = dflag[kflag] = 0;
  536.    hard_way[kflag] = term_char[kflag] = 0;
  537.    if (m1[kflag] == m1[kflag-1] && n1[kflag] == n1[kflag-1] &&
  538.     m2[kflag] == m2[kflag-1] && n2[kflag] == n2[kflag-1])
  539.    if (bflag[kflag] == bflag[kflag-1] && rflag[kflag] == rflag[kflag-1] &&
  540.     nflag[kflag] == nflag[kflag-1] && iflag[kflag] == iflag[kflag-1])
  541.    if (fflag[kflag] == fflag[kflag-1] && dflag[kflag] == dflag[kflag-1] &&
  542.     term_char[kflag] == term_char[kflag-1])
  543.    kflag--;
  544. /*** Distribution phase. Create sorted runs from the input file(s)
  545.  * to the temp file(s).
  546. */
  547.    for (;;) {
  548.       if (ifp == NULL) {
  549.      for (i=1; i<argc; ++i)    /* find next file-name argument */
  550.         if ((cp = argv[i]) != NULL)
  551.         break;
  552.      if (i >= argc)
  553.         break;
  554.      argv[i] = NULL;
  555.      if ((ifp = fopen(cp, "r")) == NULL) {
  556.         fprintf(stderr, "%s: cannot open.\n", cp);
  557.         quit();
  558.      }
  559.       }
  560.       get_in_line();        /* get line from input */
  561.       if (nlbuf >= 0) {
  562.      if (nline >= MX_RLINE
  563.       || (cp = malloc(nlbuf + sizeof(char))) == NULL) {
  564.         do {
  565.            qksort(line, nline, sizeof(line[0]), &compare);
  566.            saverun();
  567.            putline(tfp);
  568.            crp = xalloc(sizeof(struct run));
  569.            crp->r_size = 0;
  570.         } while (nline == MX_RLINE);
  571.         if (nlbuf >= 0)
  572.         cp = xalloc(nlbuf + sizeof (char));
  573.      }
  574.      if (nlbuf >= 0) {
  575.         strcpy(cp, lbuf);
  576.         nlbuf = -1;
  577.         line[nline++] = cp;
  578.      }
  579.       }
  580.    }
  581.    qksort(line, nline, sizeof (line[0]), &compare);
  582.    if (frp == NULL) { /* We have only 1 run, so put it right out. */
  583.       openoutput();
  584.       if (uflag)
  585.      llout = xalloc(sizeof(lbuf));
  586.       putline(ofp);
  587.       pr_eltim("Completed, all data fit in memory");
  588.       quit();
  589.    }
  590.  
  591. /*** Merge phase. We are all done with the input files. */
  592.    if (nline > 0) {
  593.       saverun();
  594.       putline(tfp);
  595.    }
  596.    fclose(tfp);
  597.  
  598.    pr_eltim("Distribution phase complete");
  599. #ifdef TIMER
  600.    start_time = systime();
  601. #endif
  602.    free(line);
  603.    if (uflag)
  604.       llout = xalloc(sizeof(lbuf));
  605.    openoutput();
  606.    if ((tfp = fopen(wkf[0].w_filename, "r")) == NULL)
  607.       panic("Cannot reopen temp file.\n");
  608.    heap = xalloc(nruns * sizeof(struct heap_s));
  609.  
  610. /* See how many lines can be pre-read form the various runs. All this is
  611.  * in an attempt to read several lines from a run into memory each time
  612.  * we read, because the seek time is most of the time expense of the
  613.  * merge phase.
  614.  * We are limited by: 1) the size of the h_lps array in a heap element,
  615.  * and 2) the amount of memory we have available to put these lines into.
  616.  * To arrive at the memory we have/need, allocate as much as we need.
  617.  * This will most likely fail (no way is a very large file going to
  618.  * fit in memory). This failure point defines the max # of lines we will
  619.  * be able to hold. There is a safety margin here, but bad luck could
  620.  * cause the alloc to fail during the merge. If this happens, bump up
  621.  * the safety margin. With any luck, using the average record size will
  622.  * be good enough.
  623. */
  624.    i = nruns * H_P_READ;
  625.    if (i > in_records) i = in_records;
  626.    c = in_bytes / in_records;
  627.    if (c < (sizeof(int))) c = sizeof(int);
  628.    lrp = xalloc(25 * c);    /* alloc a safety margin */
  629.    lrp->r_rp = NULL;
  630.    while (i-- && (crp = malloc(c)) != NULL) {
  631.       crp->r_rp = lrp;
  632.       lrp = crp;
  633.       max_mline++;
  634.    }
  635.    /* now free the space all up */
  636.    while (lrp != NULL) {
  637.       crp = lrp;
  638.       lrp = lrp->r_rp;
  639.       free(crp);
  640.    }
  641.  
  642.    /* Read the same number of lines initially for all runs. */
  643.    i = max_mline / nruns;
  644.    if (i <= 0) i = 1;
  645.    if (i > H_P_READ) i = H_P_READ;
  646.    rp = frp;
  647.    hp = &heap[0];
  648.    while (rp != NULL) { /* init for the merge */
  649.       hp->h_rp = rp;
  650.       run_read(hp, i);
  651.       if (hp->h_lp_a[0] == NULL)
  652.      panic("Empty run.\n");
  653.       rp = rp->r_rp;
  654.       hp++;
  655.    }
  656.    /* Sort it, to get the heap initially set up. */
  657.    qksort (heap, nruns, sizeof (struct heap_s), &compare);
  658.  
  659.    while (nruns) {
  660.       cp = heap[0].h_lp_a[0];
  661.       if (llout)
  662.      sp_fputs(cp, ofp);
  663.       else {
  664.      fputs(cp, ofp);
  665.      fputs("\n", ofp);
  666.       }
  667.       free(cp);
  668.       memcopy(&heap_tmp, &heap[0], sizeof (struct heap_s));
  669.       pre_lines--;    /* shift up the other pre-read lines */
  670.       memcopy(&heap_tmp.h_lp_a[0], &heap_tmp.h_lp_a[1],
  671.        sizeof(heap[0].h_lp_a[0]) * (H_P_READ-1));
  672.       heap_tmp.h_lp_a[H_P_READ - 1] = NULL;
  673.       if (heap_tmp.h_lp_a[0] == NULL)    /* we used them all up */
  674.      run_read(&heap_tmp, H_P_READ);
  675.       if (heap_tmp.h_lp_a[0] == NULL) { /* Done with this run. */
  676.      pr_eltim("Run complete");
  677.      --nruns;
  678.      reheap (heap, nruns, sizeof (struct heap_s), &heap[nruns]);
  679.       }
  680.       else
  681.      reheap (heap, nruns, sizeof (struct heap_s), &heap_tmp);
  682.    }
  683.    if (vflag) {
  684. #ifdef TIMER
  685.       i = (systime() - start_time) /100;    /* get&print elapsed time*/
  686.       fprintf (stderr,"Merge Elapsed: %d.%01d sec\n", i/10, i%10);
  687. #endif
  688.    }
  689.    quit();
  690. }
  691.  
  692.  
  693. /*********************************************/
  694. pr_eltim(why)
  695. char    *why;
  696. {
  697.    int i;
  698.  
  699.    if (!vflag)
  700.       return;
  701. #ifdef TIMER
  702.    i = (systime() - start_time) /100;    /* get&print elapsed time*/
  703. #endif
  704.    fprintf(stderr, "%s, %ld records, %ld bytes, run number %d.\n",
  705.     why, in_records, in_bytes, nruns);
  706. #ifdef TIMER
  707.    fprintf (stderr,"Elapsed time: %d.%01d sec\n", i/10, i%10);
  708. #endif
  709. }
  710.  
  711. /*********************************************/
  712. /* Get the next line from the input file to "lbuf".
  713.  * ifp == NULL means input file is closed.
  714.  * nlbuf == length of the line in lbuf (<0 means nothing in lbuf).
  715. */
  716. get_in_line()
  717. {
  718.    if (ifp == NULL) return;
  719.    if (fgets(lbuf, sizeof lbuf, ifp) == NULL) {
  720.       if (ifp != stdin) fclose(ifp);
  721.       ifp = NULL;
  722.       nlbuf = -1;
  723.    }
  724.    else {
  725.       lbuf[strlen(lbuf) - 1] = EOS;
  726.       nlbuf = strlen(lbuf);
  727.       in_records++; in_bytes += nlbuf;
  728.    }
  729. }
  730.  
  731. /*
  732.  * Open the output file and stash its file
  733.  * pointer in 'ofp'. If no output file is
  734.  * given 'ofp' is a dup. of 'stdout'.
  735.  */
  736. openoutput()
  737. {
  738.    if (ofn == NULL)
  739.       ofp = stdout;
  740.    else if ((ofp = fopen(ofn, "w")) == NULL) {
  741.       fprintf(stderr, "%s: cannot create.\n", ofn);
  742.       quit();
  743.    }
  744. }
  745.  
  746. /******************************************/
  747. /* Special fputs, used for '-u' flag, to put out only
  748.  * unique lines.
  749.  * The very first line is deemed 'unique', and is always put out.
  750. */
  751. sp_fputs(buf, usr_file)
  752. char *buf;
  753. FILE *usr_file;
  754. {
  755.    if (com_par(&llout, &buf, kflag? kflag-1 : kflag) || first_out) {
  756.       fputs(buf, usr_file); /* this line different from last */
  757.       fputs("\n", usr_file);
  758.       first_out = FALSE;
  759.       strcpy (llout, buf);
  760.    }
  761. }
  762.  
  763. /**************************************/
  764. /* read some lines from a run into memory */
  765. run_read(helt, m_lines)
  766. struct heap_s *helt;    /* the heap element for this run */
  767. int m_lines;        /* max # of lines to read */
  768. {
  769.    int i;
  770.  
  771.    for (i = 0; i < m_lines && pre_lines <= max_mline; i++) {
  772.       if ((helt->h_lp_a[i] = getline(helt->h_rp)) == NULL)
  773.      break;
  774.       pre_lines++;
  775.    }
  776.    if (i < H_P_READ) helt->h_lp_a[i] = NULL;
  777. }
  778.  
  779.  
  780. /************************************************/
  781. /* convert escaped char to a char value. Update cp. */
  782. esc_char (cpp)
  783. char **cpp;
  784. {
  785.    register char c;    /* the converted character */
  786.    register char c1;
  787.    register char *p;    /* buffer ptr */
  788.  
  789.    p = *cpp;    /* point to the string */
  790.    c = tolower(*p++);
  791.    if (c == 't')
  792.       c = '\t';            /* \t is tab */
  793.    else if (c == 's')
  794.       c = ' ';            /* \s is space */
  795.    else if (c >= '0' && c <= '7') { /*  \digits is the obvious */
  796.       c -= '0';
  797.       while ((c1 = *p++) >= '0' && c1 <= '7')
  798.      c = (c<<3) + (c1 - '0');
  799.       p--;            /* back up, we went too far */
  800.    }
  801.    else            /* anything else is itself */
  802.       c = *(p-1);
  803.    *cpp = p;        /* update the buffer pointer */
  804.    return (c);
  805. }
  806.  
  807.  
  808.  
  809.  
  810.  
  811.  
  812.  
  813.  
  814.  
  815.  
  816.  
  817.  
  818.  
  819.  
  820.  
  821.  
  822.  
  823.  
  824. /******************** routines passed into quicksort *******/
  825. /*
  826.  * Compare routine.
  827.  */
  828. static int     compare(sa, sb)
  829. char *sa[], *sb[];
  830. {
  831.    return (com_par(sa, sb, kflag));
  832. }
  833.  
  834.  
  835.  
  836. static int     com_par(sa, sb, num_keys)
  837. char *sa[], *sb[];
  838. int num_keys;    /* max number of keys to examine */
  839. {
  840.    extern char *get_to_key();
  841.    register char *a, *b;
  842.    register c;
  843.    char ch;
  844.    long d, atol();
  845.    int field_num;            /* field number loop counter */
  846.    char *aeok_ptr, *beok_ptr;    /* for saving the char after the key */
  847.    char aeok_char, beok_char;
  848.  
  849.    c = 0;
  850.    for (field_num = 0; !c && (field_num <= num_keys); field_num++) {
  851.       /* find the key-field addresses */
  852.       aeok_ptr = beok_ptr = &ch;    /* in case EOK = EOL */
  853.       a = get_to_key(m1[field_num], n1[field_num],
  854.        m2[field_num], n2[field_num],
  855.        bflag[field_num], *sa, &aeok_ptr, term_char[field_num]);
  856.       b = get_to_key(m1[field_num], n1[field_num],
  857.        m2[field_num], n2[field_num],
  858.        bflag[field_num], *sb, &beok_ptr, term_char[field_num]);
  859.       aeok_char = *aeok_ptr; *aeok_ptr = NULL;    /* terminate keys */
  860.       beok_char = *beok_ptr; *beok_ptr = NULL;    /* terminate keys */
  861.       /*fprintf(stderr,"a key:'%s'\n", a);*/
  862.  
  863.       if (nflag[field_num]) {
  864.      if ((d = atol(a)-atol(b)) < 0)
  865.         --c;
  866.      else if (d > 0)
  867.         ++c;
  868.       }
  869.       else if (hard_way[field_num])
  870.      c = hard_cmp(a, b, iflag[field_num], dflag[field_num],
  871.        fflag[field_num]);
  872.       else
  873.      c = strcmp(a, b);
  874.       /* restore the char after the keys */
  875.       *aeok_ptr = aeok_char;
  876.       *beok_ptr = beok_char;
  877.       if (rflag[field_num])
  878.      c = -c;
  879.    }
  880.    return (c);
  881. }
  882.  
  883. /***************/
  884. /* return pointer to the next field of the string.
  885.  * A field is defined as: optional whitespace followed by
  886.  *    non-whitespace; the next field is the next
  887.  *    whitespace or NULL.
  888.  *
  889.  * The returned result is a pointer to this 1st char of the
  890.  * next field.
  891.  * It will never advance past the trailing NULL.
  892. */
  893. char *nxt_fld(s, tch)
  894. register char *s;
  895. register char tch;    /* field terminator char or NULL */
  896. {
  897.    register char c;
  898.  
  899.    if (tch != NULL) {
  900.       while (*s != NULL && *s++ != tch) ;
  901.    }
  902.    else
  903.       {
  904.       while (((c=*s) != NULL) && iswhite(c)) s++;
  905.       while (((c=*s) != NULL) && !iswhite(c)) s++;
  906.    }
  907.    return (s);
  908. }
  909.  
  910. /*****************************************/
  911. /* whitespace is anything not between space & 0177 */
  912. iswhite(c)
  913. register char c;
  914. {
  915.    /* make it an unsigned byte */
  916.    c &= 0377;
  917.    return ( (c <= ' ') || (0177 <= c));
  918. }
  919. /*****************************************/
  920. /********* get the definition for a key field
  921. */
  922. defin_key(cp)
  923. char *cp;
  924. {
  925.    if (kflag >= MAX_KEYS - 1)
  926.       panic ("Too many keys specified\n");
  927.  
  928.    n1[kflag] = n2[kflag] = 0; m2[kflag] = -1;
  929.    m1[kflag] = atodl(&cp);
  930.    if (*cp == '.') {
  931.       cp++;        /* char adv from start of field */
  932.       n1[kflag] = atodl(&cp);
  933.    }
  934.    if (!*cp++)    return;    /* no end-of-key */
  935.  
  936.    m2[kflag] = atodl(&cp);
  937.    if (!*cp) return;
  938.    if (*cp++ != '.')
  939.       panic ("Invalid key field format\n");
  940.    n2[kflag] = atodl(&cp);
  941.  
  942.    return;
  943. }
  944.  
  945. /*****************/
  946. /* unsigned ascii to decimal conversion.
  947.  * stops on a non-digit. Update the buffer pointer to
  948.  * point to this terminating non-digit.
  949. */
  950. int atodl(cp)
  951. char **cp;
  952. {
  953.    register int n;
  954.    register char *p;
  955.    register char ch;
  956.  
  957.    n = 0;
  958.    p = *cp;    /* point to the string */
  959.    while (isdigit((ch = *p++)))
  960.       n = 10*n + (ch - '0');
  961.    *cp = p-1;    /* update the buffer pointer */
  962.    return (n);
  963. }
  964.  
  965. /************************************************/
  966. /* get pointers to the start-of-key, and end-of-key.
  967.  * returns ptr to 1st char of the key.
  968.  * "eok_ptr" points to next char after the key, unless eok = "end-of-line".
  969.  * The pointers will never go past the NULL.
  970.  * eok-ptr will never be before sok-ptr.
  971. */
  972. char *get_to_key (sok_fld, sok_adv, eok_fld, eok_adv, skip_ws,
  973.      str, eok_ptr, term_ch)
  974. int sok_fld, sok_adv;    /* start-of-key fields & chars to skip*/
  975. int eok_fld, eok_adv;    /* end-of-key fields & chars to skip*/
  976. int skip_ws;        /* skip leading whitespace before advancing by chars*/
  977. char *str;        /* the string */
  978. char **eok_ptr;    /* set to point to the 1st char after the key,
  979.          * if any eok was specified. 
  980.          * otherwise not modified. */
  981. char term_ch;        /* field terminator or NULL */
  982. {
  983.    register char *kptr;    /* start-of-key pointer */
  984.    register char *eptr;    /* end-of-key pointer */
  985.    register int i;
  986.    char ch;
  987.  
  988. /* skip over fields to get to start-of-key */
  989.    kptr = str;    /* init to start of line */
  990.    i = sok_fld;
  991.    while (i--) kptr = nxt_fld(kptr, term_ch);
  992.    /* probably we can keep going forward from the SOK to EOK field */
  993.    i = eok_fld - sok_fld;    eptr = kptr;
  994. /* advance SOK ptr by chars (never past end) */
  995.    if (skip_ws)
  996.       while ((ch=*kptr) && iswhite(ch)) kptr++;
  997.    while (sok_adv-- && *kptr++);
  998.    if (eok_fld >= 0) { /* position to eok field*/
  999.       if (i < 0) {
  1000.      i = eok_fld;    /* eok search from start of line */
  1001.      eptr = str;
  1002.       }
  1003.       while (i--) eptr = nxt_fld(eptr, term_ch);
  1004.       /* advance eok ptr by chars (never past end) */
  1005.       if (skip_ws)
  1006.      while ((ch=*eptr) && iswhite(ch)) eptr++;
  1007.       while (eok_adv-- && *eptr++);
  1008.       *eok_ptr = eptr;    /* return ptr to char after key */
  1009.       if (eptr < kptr)
  1010.      *eok_ptr = kptr;    /* force null key */
  1011.    }
  1012.    return (kptr);
  1013. }
  1014.  
  1015. /*************************************************************/
  1016. /* string comparisons the hard-way, one character at a time, 
  1017.  * because one of the special flags was set.
  1018. */
  1019. hard_cmp(a, b, ifl, dfl, ffl)
  1020. register char *a, *b;    /* the two strings to compare */
  1021. int ifl;    /* ignore all whitespace */
  1022. int dfl;    /* dictionary order, ignore all but letters, digits,
  1023.         * and blanks
  1024.         */
  1025. int ffl;    /* fold upper-case to lower case before compare */
  1026. {
  1027.    register char achar, bchar;
  1028.    int c;    /* result */
  1029.  
  1030.    c = 0;
  1031.    while (!c && (achar = *a) && (bchar = *b)) {
  1032.       if (dfl) {    /* dictionary-style */
  1033.      while ((achar = *a) && !(isdigit(achar) ||
  1034.           isalpha(achar) || (achar == ' '))) a++;
  1035.      while ((bchar = *b) && !(isdigit(bchar) ||
  1036.           isalpha(bchar) || (bchar == ' '))) b++;
  1037.       }
  1038.       if (ifl) {    /* ignore all whitespace */
  1039.      while ((achar = *a) && iswhite(achar)) a++;
  1040.      while ((bchar = *b) && iswhite(bchar)) b++;
  1041.       }
  1042.       if (ffl) {    /* fold to lower-case */
  1043.      achar = tolower(achar);
  1044.      bchar = tolower(bchar);
  1045.       }
  1046.       c = achar - bchar;
  1047.       if (!c && achar) a++;
  1048.       if (!c && bchar) b++;
  1049.    }
  1050.    if (!c) c = achar - bchar;
  1051.    return(c);
  1052. }
  1053.  
  1054.  
  1055.  
  1056.  
  1057.  
  1058.  
  1059.  
  1060.  
  1061.  
  1062.  
  1063.  
  1064. /*
  1065.  * Rebuild a heap.
  1066.  * This is essentially TREESORT.
  1067.  * Used to reorder the heap when a new item
  1068.  * is read into it.
  1069.  * The 'heap' is a binary tree, such that for each node 'i', the key at
  1070.  * 'i' is the lowest of it and it's two sons, (2*i + 1) and (2*i + 2).
  1071.  * The new element is to be inserted where it should go.
  1072.  * We can move things up in the heap, as array element [0] is empty.
  1073.  * At each step, h[i] is empty.
  1074.  */
  1075.  
  1076. reheap(h, n, elt_size, new_elt)
  1077. BYTE h[];        /* The array which is the heap */
  1078. int n;            /* number of elements in array h*/
  1079. int elt_size;        /* size of array element in bytes */
  1080. struct heap_s *new_elt;    /* new element to be added */
  1081. {
  1082.    register int i, j;
  1083.    BYTE *ip, *jp, *jp1;    /* ptrs for i, j, j+1 */
  1084.  
  1085.    for (i = 0, ip = h; (j = 2*i+1) < n; i = j, ip = jp) {
  1086.       jp = h+(j*elt_size);
  1087.       jp1 = jp + elt_size;
  1088.       if ((j+1 < n) && (compare(jp1, jp) < 0)) {
  1089.      jp = jp1;
  1090.      ++j;
  1091.       }
  1092.       /* j now points to the smaller child of i */
  1093.       if (compare(new_elt, jp) <= 0)
  1094.      break;
  1095.       memcopy(ip, jp, elt_size);
  1096.    }
  1097.    memcopy(ip, new_elt, elt_size);
  1098. #ifdef    TREEVER    /**** verify that the tree is ok */
  1099.    for (i = 0; (j = 2*i+1) < nruns; i++) {
  1100.       if (h != heap) break;
  1101.       if ((j < nruns && compare(&heap[i].h_lp, &heap[j].h_lp) > 0) ||
  1102.        (j+1 < nruns && compare(&heap[i].h_lp,&heap[j+1].h_lp) > 0)) {
  1103.      fprintf (stderr, "Tree out of order. n = %d. Index = %d.\n",
  1104.           nruns, i);
  1105.      fprintf (stderr,"addresses: %o %o %o\n", &heap[i], &heap[j],
  1106.           &heap[j+1]);
  1107.      fprintf (stderr,"nruns: %d\n%d->%s%d->%s%d->%s", nruns,
  1108.           i,heap[i].h_lp,j,heap[j].h_lp,j+1,
  1109.           j+1<nruns ? heap[j+1].h_lp : NULL);
  1110.      fprintf (stderr,"New->%s", new_elt->h_lp);
  1111.      fprintf (stderr,"At %o\n", new_elt);
  1112.      fprintf (stderr,"%d->%s", 0, heap[0].h_lp);
  1113.      for (i = 0; i <n; i++) {
  1114.         fprintf (stdout, "%d->%s", i, heap[i].h_lp);
  1115.      }
  1116.      abort();
  1117.       }
  1118.    }
  1119.    for (i = 0; (j = 2*i+1) < nline; i++) {
  1120.       if (h != line) break;
  1121.       if ((j < nline && compare(&line[i], &line[j]) > 0) ||
  1122.        (j+1 < nline && compare(&line[i],&line[j+1]) > 0)) {
  1123.      fprintf (stderr, "Tree out of order. n = %d. Index = %d.\n",
  1124.           nline, i);
  1125.      fprintf (stderr,"addresses: %o %o %o\n", &line[i], &line[j],
  1126.           &line[j+1]);
  1127.      fprintf (stderr,"nline: %d\n%d->%s%d->%s%d->%s", nline,
  1128.           i,line[i],j,line[j],j+1,
  1129.           j+1<nline ? line[j+1] : NULL);
  1130.      for (i = 0; i <n; i++) {
  1131.         fprintf (stdout, "%d->%s", i, line[i]);
  1132.      }
  1133.      abort();
  1134.       }
  1135.    }
  1136. #endif
  1137. }
  1138.  
  1139. /*
  1140.  * Save a run.
  1141.  * The run block has been preallocated
  1142.  * because there may not be enough space
  1143.  * to allocate it now.
  1144.  */
  1145. saverun()
  1146. {
  1147.    long ftell();
  1148.  
  1149.    crp->r_rp = NULL;
  1150.    crp->r_seek = ftell(tfp);
  1151.    if (frp == NULL)
  1152.       frp = crp;
  1153.    else
  1154.       lrp->r_rp = crp;
  1155.    lrp = crp;
  1156.    ++nruns;
  1157. }
  1158.  
  1159. /*
  1160.  * Get a line from the specified run
  1161.  * on the temp. file.
  1162.  * Pack the line into allocated storage
  1163.  * and return a pointer to it.
  1164.  * Return NULL if there are no lines left
  1165.  * in the run; real end of file is an
  1166.  * internal botch.
  1167.  */
  1168. char *getline(rp)
  1169. register struct run *rp;
  1170. {
  1171.    register char *cp;
  1172.    long ftell();
  1173.  
  1174.    if (rp->r_size == 0)
  1175.       return (NULL);
  1176.    fseek(tfp, rp->r_seek, 0);
  1177.    if (fgets(lbuf, sizeof lbuf, tfp) == NULL)
  1178.       panic("Unexpected end of file\n");
  1179.    lbuf[strlen(lbuf) - 1] = EOS;
  1180.    rp->r_seek = ftell(tfp);
  1181.    --rp->r_size;
  1182.    cp = xalloc(strlen(lbuf) + sizeof(char));
  1183.    strcpy(cp, lbuf);
  1184.    return (cp);
  1185. }
  1186.  
  1187. /*************************/
  1188. /* Dump the lines in the array to the file.    */
  1189. putline(fp)
  1190. FILE *fp;    /* the output fp */
  1191. {
  1192.    register int ilater;    /* ptr for lines that can't go in this run */
  1193.    register int i;
  1194.    register char *cp;
  1195. #ifdef REPLPUT
  1196.    char *ncp;
  1197. #endif
  1198.  
  1199.    crp->r_size = nline;
  1200. #ifndef REPLPUT
  1201.    for (i=0; i<nline; i++) {
  1202.       cp = line[i];
  1203.       if (llout)
  1204.      sp_fputs(cp, fp);
  1205.       else {
  1206.      fputs(cp, fp);
  1207.      fputs("\n", fp);
  1208.       }
  1209.       free(cp);
  1210.    }
  1211.    nline = 0;
  1212. #else
  1213.  
  1214. /*
  1215.  * To improve the length of the runs, replace each line as it goes out.
  1216.  * If it can, it will become part of this run, otherwise it will be
  1217.  * saved up to be part of the next run.
  1218.  *
  1219.  * In general, when this routine returns, the array will be filled with
  1220.  * lines that wouldn't go in this run. This will be the case except when
  1221.  * we hit EOF on the input.
  1222.  *
  1223.  * The next input line is already in lbuf.
  1224. */
  1225.    ilater = MX_RLINE;
  1226.    while (nline > 0) {
  1227.       cp = line[0];
  1228.       if (llout)
  1229.      sp_fputs(cp, fp);
  1230.       else {
  1231.      fputs(cp, fp);
  1232.      fputs("\n", fp);
  1233.       }
  1234.       if (nlbuf >= 0 && crp->r_size < 30000 &&
  1235.        (ncp = malloc(nlbuf + sizeof(char))) != NULL) {
  1236.      strcpy(ncp, lbuf);
  1237.      get_in_line();
  1238.      if (compare(&ncp, &cp) >= 0) { /* the line can be in this run */
  1239.         crp->r_size++;
  1240.         reheap(line, nline, sizeof(line[0]), &ncp);
  1241.      }
  1242.      else {    /* it will be part of the next run */
  1243.         nline--;
  1244.         reheap (line, nline, sizeof(line[0]), &line[nline]);
  1245.         line[--ilater] = ncp;    /* tuck it away */
  1246.      }
  1247.       }
  1248.       else {    /* nothing to replace with */
  1249.      nline--;
  1250.      reheap(line, nline, sizeof(line[0]), &line[nline]);
  1251.       }
  1252.       free(cp);
  1253.    }
  1254.  
  1255. /* The new replacement lines that couldn't become part of
  1256.  * this run are at the end of the array. Move them up and adjust the
  1257.  * index.
  1258. */
  1259.    nline = MX_RLINE - ilater;
  1260.    if (nline != 0 && ilater != 0)
  1261.       memcopy(&line[0], &line[ilater], nline * sizeof(line[0]));
  1262. #endif
  1263. }
  1264.  
  1265. /*
  1266.  * Allocate space.
  1267.  * If no space, abort with a nasty
  1268.  * little message.
  1269.  */
  1270. char *xalloc(n)
  1271. {
  1272.    register char *p;
  1273.  
  1274.    if ((p = malloc(n)) == NULL) {
  1275.       fprintf(stderr, "Out of space.\n");
  1276.       exit(1);
  1277.    }
  1278.    return (p);
  1279. }
  1280.  
  1281. /*
  1282.  * Quit.
  1283.  * Get rid of the temp. file.
  1284.  * Exit.
  1285.  */
  1286. quit()
  1287. {
  1288.    if (tfp != NULL)
  1289. #if AMIGA || unix
  1290.       unlink (wkf[0].w_filename);
  1291. #else
  1292.       fmkdl(tfp);
  1293. #endif
  1294.    exit(0);
  1295. }
  1296.  
  1297. /*
  1298.  * Tell the user just what is expected
  1299.  * of him.
  1300.  */
  1301. usage(why, argsave, c)
  1302. char        *why;
  1303. char        *argsave;
  1304. char        c;
  1305. {
  1306.    if (c != '?') {
  1307.       fprintf(stderr, "Sort error: %s", why);
  1308.       if (c == EOS)
  1309.          fprintf(stderr, "\nat end of option string");
  1310.       else if (c < ' ')
  1311.          fprintf(stderr, " at CTRL/%c", c + '@');
  1312.       else fprintf(stderr, " at '%c'", c);
  1313.       fprintf(stderr, ", argument = \"%s\"\n", argsave);
  1314.    }
  1315.    fprintf(stderr, "Usage: sort [-bdfinrt?uv] [-[bdfinrt?]km1.n1,m2.n2]");
  1316.    fprintf (stderr, " [-k...]\n\t    [-oOUTFILE] [file ...]\n");
  1317.    if (c == '?') {
  1318.       prtdoc();
  1319.    }
  1320.    exit(1);
  1321. }
  1322. /*
  1323.  * Errors.
  1324.  * Print a message and die with "error" status on RT/RSX,
  1325.  * "error" on UNIX (I think).
  1326.  */
  1327. errxit(a)
  1328.    {
  1329.    fprintf(stderr,"?SORT-F-%r", &a);
  1330. #ifdef decus                           /* Exit status per rt/rsx/unix */
  1331. #ifdef rt11
  1332.    exit(4);
  1333. #endif
  1334. #ifdef rsx
  1335.    exit(2);
  1336. #endif
  1337. #else
  1338.    exit(0);
  1339. #endif
  1340.    }
  1341.  
  1342. /*
  1343.  * Fatal errors.
  1344.  * Print a message and die.
  1345.  */
  1346. panic(a)
  1347. {
  1348.    fprintf(stderr, "Panic: %r", &a);
  1349. #ifdef decus                           /* Exit status per rt/rsx/unix */
  1350. #ifdef rt11
  1351.    exit(8);
  1352. #endif
  1353. #ifdef rsx
  1354.    exit(4);
  1355. #endif
  1356. #else
  1357.    exit(0);
  1358. #endif
  1359. }
  1360.  
  1361. #ifdef TIMER
  1362. static int        time_first = TRUE;
  1363. static struct timeb    first_time;
  1364.  
  1365. long int
  1366. systime()
  1367. /*
  1368.  * Returns elapsed time in milliseconds
  1369.  */
  1370. {
  1371.     long        time, millisec;
  1372.     struct timeb    time_buffer;
  1373.  
  1374.     if (time_first) {
  1375.         /*
  1376.          * This makes sure we can store enough milliseconds in 32 bits
  1377.          */
  1378.         ftime(&first_time);
  1379.         time_first = FALSE;
  1380.     }
  1381.     ftime(&time_buffer);
  1382.     time = time_buffer.time - first_time.time;
  1383.     millisec = time_buffer.millitm - first_time.millitm;
  1384.     time *= 1000;
  1385.     return (time + millisec);
  1386. }
  1387. #endif    /* TIMER */
  1388.  
  1389. prtdoc ()
  1390. {
  1391.     register char *dp;
  1392.  
  1393.     for (dp = documentation; *dp; dp++) {
  1394.         printf ("%s\n", *dp);
  1395.     }
  1396. }
  1397.  
  1398. #ifndef unix
  1399. memcopy (out, in, size)
  1400. char *out;
  1401. char *in;
  1402. int size;
  1403. {
  1404. #ifdef AMIGA
  1405.    movmem (in, out, size);
  1406. #else
  1407.    while (size-- > 0) {
  1408.     *out++ = *in++;
  1409.    }
  1410. #endif
  1411. }
  1412. #endif
  1413.